#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

//class Solution {
//private:
    int cnt = 0;
    void backtracking(vector<int>& nums, int target, int startIndex, int sum)
    {
        if (startIndex == nums.size() && target == sum)
        {
            cnt++;
        }
        for (size_t i = startIndex; i < nums.size(); i++)
        {
            backtracking(nums, target, i + 1, sum + nums[i]);
            backtracking(nums, target, i + 1, sum - nums[i]);
        }
    }
//public:

    int findTargetSumWays(vector<int>& nums, int target) {
        backtracking(nums, target, 0, 0);

        return cnt;
    }

    
//};


int main()
{
    vector<int> nums = { 1,1,1,1,1 };
    int p = findTargetSumWays(nums, 3);
    return 0;
}